package com.example.demo.arithmetic.hash;

import java.util.HashMap;
import java.util.Map;

public class IsomorphicStrings {
    public static boolean isIsomorphic(String s, String t) {
        // 如果字符串长度不同，则它们不可能是同构的  
        if (s.length() != t.length()) {
            return false;
        }

        // 创建两个哈希表来跟踪映射关系  
        // 但实际上我们只需要一个哈希表，因为我们可以直接检查映射是否一致  
        Map<Character, Character> charMap = new HashMap<>();

        // 遍历两个字符串的每一个字符  
        for (int i = 0; i < s.length(); i++) {
            char sc = s.charAt(i);
            char tc = t.charAt(i);

            // 检查 s 的字符是否已经有映射  
            if (charMap.containsKey(sc)) {
                // 如果已经有映射，则检查映射是否一致  
                if (charMap.get(sc) != tc) {
                    return false; // 映射不一致，不是同构的  
                }
            } else {
                // 如果 s 的字符还没有映射，则检查 t 的字符是否已经被映射过  
                if (charMap.containsValue(tc)) {
                    return false; // t 的字符已经被映射过，不是同构的  
                }
                // 添加新的映射关系  
                charMap.put(sc, tc);
            }
        }

        // 遍历完成后，没有发现不一致的映射，所以是同构的  
        return true;
    }

    public static boolean isIsomorphic2(String s, String t) {
        Map<Character, Character> s2t = new HashMap<>(), t2s = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char a = s.charAt(i), b = t.charAt(i);
            // 对于已有映射 a -> s2t[a]，若和当前字符映射 a -> b 不匹配，
            // 说明有一对多的映射关系，则返回 false ；
            // 对于映射 b -> a 也同理
            if (s2t.containsKey(a) && s2t.get(a) != b ||
                    t2s.containsKey(b) && t2s.get(b) != a)
                return false;
            s2t.put(a, b);
            t2s.put(b, a);
        }
        return true;
    }


    public static void main(String[] args) {
        String s1 = "egg";
        String t1 = "add";
        System.out.println(isIsomorphic(s1, t1)); // 输出: true  

        String s2 = "foo";
        String t2 = "bar";
        System.out.println(isIsomorphic(s2, t2)); // 输出: false  

        String s3 = "paper";
        String t3 = "title";
        System.out.println(isIsomorphic(s3, t3)); // 输出: true  
    }
}